package cczxsong;

        import edu.princeton.cs.algs4.StdIn;
        import edu.princeton.cs.algs4.StdOut;
        import edu.princeton.cs.algs4.StdRandom;

        import java.util.Arrays;

class Sort {
    protected static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    protected static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    protected static void show(Comparable[] a) {
        for (int i = 0; i < a.length; i++)
            StdOut.print(a[i] + " ");
        StdOut.println();
    }

    protected static boolean isSorted(Comparable[] a) {
        for (int i = 1; i < a.length; i++)
            if (less(a[i], a[i - 1])) return false;
        return true;
    }

    public static void merge(Comparable[] a, int lo, int mid, int hi) {

        // copy to aux[]
        Comparable[] aux = new Comparable[a.length];
        for (int k = lo; k <= hi; k++) {
            aux[k] = a[k];
        }
        // merge back to a[]
        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            if (i > mid) a[k] = aux[j++];  // this copying is unneccessary
            else if (j > hi) a[k] = aux[i++];
            else if (less(aux[j], aux[i])) a[k] = aux[j++];
            else a[k] = aux[i++];
        }

    }

    public static double time(String alg, Comparable[] a) {
        long StartTime = System.nanoTime();
        if (alg.equals("Insertion")) Insertion.sort(a);
        if (alg.equals("Merge__BU")) MergeBU.sort(a);
        if (alg.equals("Merge__TD")) MergeTD.sort(a);
        if (alg.equals("QuickSort")) QuickSort.sort(a);
        if (alg.equals("Quick3way")) QuickSort_3way.sort(a);
        long endTime = System.nanoTime();
        StdOut.println(alg + ":");
        StdOut.println("UsedTime->:" + (endTime - StartTime) / 1000 + " μs");
        return 0;
    }
    public static double memo(String alg, Comparable[] a) {
        Runtime run = Runtime.getRuntime();
        run.gc();
        long startMemo = run.totalMemory() - run.freeMemory();
        if (alg.equals("Insertion")) Insertion.sort(a);
        if (alg.equals("Merge__BU")) MergeBU.sort(a);
        if (alg.equals("Merge__TD")) MergeTD.sort(a);
        if (alg.equals("QuickSort")) QuickSort.sort(a);
        if (alg.equals("Quick3way")) QuickSort_3way.sort(a);
        long endMemo = run.totalMemory() - run.freeMemory();
        StdOut.println(alg + ":");
        StdOut.println("UsedMemo->:" + (endMemo - startMemo) + " KB");
        return 0;
    }
}

class Insertion extends Sort {

    public static void sort(Comparable[] a) {
        // StdOut.println("I am Insertion");
        int n = a.length;
        for (int i = 0; i < n; i++) {
            for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) {
                exch(a, j, j - 1);
            }
        }
    }
}

class MergeTD extends Sort {
    //    private static int CUTOFF = 7;
    public static void sort(Comparable[] a) {

        sort(a, 0, a.length - 1);
    }

    public static void sort(Comparable[] a, int lo, int hi) {
        //StdOut.println("I am MergeTD");
//        if (hi <= lo + CUTOFF-1) {
//            Insertion.sort(a);
//            return;
//        }
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        sort(a, lo, mid);
        sort(a, mid + 1, hi);

        merge(a, lo, mid, hi);
    }
}


class MergeBU extends Sort {

    public static void sort(Comparable[] a) {
        // StdOut.println("I am MergeBU");
        int n = a.length;
        for (int sz = 1; sz < n; sz *= 2) {
            for (int lo = 0; lo < n - sz; lo += sz + sz) {
                int mid = lo + sz - 1;
                int hi = Math.min(lo + sz + sz - 1, n - 1);
                merge(a, lo, mid, hi);
            }
        }
    }
}

class QuickSort extends Sort {

    public static void sort(Comparable[] a) {
        StdRandom.shuffle(a);
        sort(a, 0, a.length - 1);
    }

    private static void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo) return;
        int j = partition(a, lo, hi);
        sort(a, lo, j - 1);
        sort(a, j + 1, hi);
    }

    private static int partition(Comparable[] a, int lo, int hi) {
        int i = lo;
        int j = hi + 1;
        Comparable v = a[lo];
        while (true) {

            while (less(a[++i], v)) {
                if (i == hi) break;
            }


            while (less(v, a[--j])) {
                if (j == lo) break;
            }

            if (i >= j) break;

            exch(a, i, j);
        }

        exch(a, lo, j);
        return j;
    }
}

class QuickSort_3way extends Sort {
    public static void sort(Comparable[] a) {
        StdRandom.shuffle(a);
        sort(a, 0, a.length - 1);
        assert isSorted(a);
    }

    private static void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo) return;
        int lt = lo, gt = hi;
        Comparable v = a[lo];
        int i = lo + 1;
        while (i <= gt) {
            int cmp = a[i].compareTo(v);
            if (cmp < 0) exch(a, lt++, i++);
            else if (cmp > 0) exch(a, i, gt--);
            else i++;
        }
        sort(a, lo, lt - 1);
        sort(a, gt + 1, hi);
    }
}

//-------------------------------------test class-----------------------------------------//
public class Exp2_Sort {
    public static void main(String[] args) {
//        StdOut.println("请输入排序规模：");
//        int N = StdIn.readInt();
        int N = 10;
        Comparable array[] = new Comparable[N];

        for (int i = 0; i < N; i++) {
            array[i] = StdRandom.uniform(10);
        }
        System.out.println(Arrays.toString(array));
        Comparable[] A1 = array.clone();
        Comparable[] B1 = array.clone();
        Comparable[] C1 = array.clone();
        Comparable[] D1 = array.clone();
        Comparable[] E1 = array.clone();

//        Comparable[] A2 = array.clone();
//        Comparable[] B2 = array.clone();
//        Comparable[] C2 = array.clone();
//        Comparable[] D2 = array.clone();
//        Comparable[] E2 = array.clone();

        Sort.time("Insertion", A1);
        Sort.time("Merge__TD", B1);
        Sort.time("Merge__BU", C1);
        Sort.time("QuickSort", D1);
        Sort.time("Quick3way", E1);

//        Sort.memo("Insertion", A2);
//        Sort.memo("Merge__TD", B2);
//        Sort.memo("Merge__BU", C2);
//        Sort.memo("QuickSort", D2);
//        Sort.memo("Quick3way", E2);
    }
}

